package algorithm;

import java.util.Arrays;

/**
 * @author fangkun
 * @create 2022-05-13-11:29
 *
 * 1024
 * 给定⼀个⽬标区间和若⼲⼩区间，如何通过裁剪和组合⼩区间拼凑出⽬标区间？最少需要
 * ⼏个⼩区间？
 * 贪心
 */
public class VideoStitching {
    public static void main(String[] args) {
        int[][] clips = new int[][]{{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
        int i = videoStitching(clips, 10);
        System.out.println(i);
    }

    static int videoStitching(int[][] clips, int time) {

        if (time == 0) return 0;

        // 按起点升序排列，起点相同的终点降序排列
        Arrays.sort(clips, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        // 记录选择的短视频个数
        int res = 0;
        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.length;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪⼼选择下⼀个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下⼀个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if (curEnd >= time) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // ⽆法连续拼出区间 [0, T]
        return -1;
    }

}
